package aws;

/**
 * 有序数组中找到数字的起始下标
 */
public class TheStartIndxOfNum {

    public static void main(String[] args) {
        int [] array = {8,8,8,8,8,8,10,11,15,17,20};
        System.out.println(new TheStartIndxOfNum().findStartIndex(array, 8));
    }
    private int findStartIndex(int []array, int num) {
        int index = binSearch(array, 0, array.length-1, num);
        if(index == -1) {
            return -1;
        }
        int i = index;
        while (i >=0) {
            if(array[i] == num) {
                i--;
                continue;
            }
            break;
        }
        return i+1;
    }

    /**
     * 二分查找，找到一个坐标
     */
    private int binSearch(int []array, int low, int high, int num) {
        int middle = (low + high) / 2;
        int middleValue = array[middle];
        if(middleValue == num) {
            return middle;
        } else if(middleValue > num) {
            return binSearch(array, low, middle - 1, num);
        } else if(middleValue < num) {
            return binSearch(array, middle + 1, high, num);
        } else {
            return -1;
        }
    }
}
